package com.lw.leetcode.sort;


/**
 * 堆排序
 *
 * @Author liw
 * @Version 1.0
 */
public class HeapSort {

    // 1 1 2 6
    // 1 2 6 24
    public static void main(String[] args) {
        int[] arr = {10, 9, 8, 7, 6, 11, 6};
        heapSort(arr);
    }

    private static void heapSort(int[] arr) {
        int length = arr.length;
        for (int i = (length / 2) - 1; i >= 0; i--) {
            adjust(arr, i, length - 1);
        }
        for (int i = length - 1; i > 0; i--) {
            int item = arr[0];
            arr[0] = arr[i];
            arr[i] = item;
            adjust(arr, 0, i - 1);
        }
    }

    /**
     * 递归 调整
     *
     * @param arr    数组
     * @param index  调整的根节点
     * @param length 调整的数组长度
     */
    private static void adjust(int[] arr, int index, int length) {
        int child = index * 2 + 1;
        if (child > length) {
            return;
        }
        child = child + 1 <= length && arr[child + 1] > arr[child] ? child + 1 : child;
        if (arr[index] < arr[child]) {

            int item = arr[index];
            arr[index] = arr[child];
            arr[child] = item;
            adjust(arr, child, length);
        }
    }

    /**
     * 非递归 调整
     *
     * @param arr    数组
     * @param index  调整的根节点
     * @param length 调整的数组长度
     */
    private static void adjust2(int[] arr, int index, int length) {
        int temp = arr[index];
        int child = 2 * index + 1;
        while (child < length) {
            child = child + 1 <= length && arr[child + 1] > arr[child] ? child + 1 : child;
            if (temp >= arr[child]) {
                break;
            }
            arr[index] = arr[child];
            index = child;
            child = 2 * index + 1;
        }
        arr[index] = temp;
    }

}
